package cn.dlc.com.sort;

import java.util.Arrays;

/**
 * @author 邓立川
 * @date 2021/3/14 11:49
 * @desc 归并排序{8,4,5,7,1,3,6,2}
 */
public class Demo13 {

    // 归并的时候需要的辅助数组
    private static Comparable[] temp;

    public static void main(String[] args) {
        Integer[] arr = {9,1,2,5,7,4,8,6,3,5};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(Comparable[] arr){
        // 初始化辅助数组
        temp = new Comparable[arr.length];
        // 定义一个low和一个high,分别记录最小和最大的索引值
        int minIndex = 0;
        int maxIndex = arr.length -1;
        sort(arr, minIndex, maxIndex);

    }

    // 重载一个分组方法。这个方法用来递归，其实就是一直拆分（从中间拆开）
    private static void sort(Comparable[] arr, int minIndex, int maxIndex) {
        // 如果minIndex和maxIndex相等，结束递归
        if(minIndex >= maxIndex) {
            return;
        }

        // 获取分组后的组的中间索引
        int midIndex = minIndex + (maxIndex - minIndex) / 2;
        // 根据中间的组继续分组，同时继续对分组后的继续分组
        sort(arr, minIndex, midIndex );
        sort(arr, midIndex+1, maxIndex);

        // 在把数组进行归并
        merge(arr, minIndex, midIndex, maxIndex);
    }

    /**
     * 归并
     * @param arr
     * @param minIndex 最小索引
     * @param midIndex 中间位置
     * @param maxIndex 最大索引
     */
    private static void merge(Comparable[] arr, int minIndex, int midIndex, int maxIndex) {
        // 定义三个指针

        // 用来指向temp数组
        int i = minIndex;

        // 用来指向分组后的左边数组
        int leftIndex = minIndex;

        // 用来指向分组后的右边数组的第一个元素
        int rightIndex = midIndex + 1 ;

        while(leftIndex <= midIndex && rightIndex <= maxIndex) {
            //当这两个数组都没有遍历到最后一位的时候，比较对应的值
            if(SortUtils.lesser(arr[leftIndex],arr[rightIndex])) {
                // 左边组的小，将左边组的元素放到辅助数组temp里面去
                // 同时左边数组的指针和temp的指针后移
                temp[i++] = arr[leftIndex++];
            } else {
                // 右边组的小，将右边组的元素放到辅助数组temp里面去
                // 同时右边组的指针和temp的指针后移
                temp[i++] = arr[rightIndex++];
            }
        }

        // 如果遍历完了，但是左边还剩下一些元素
        while(leftIndex <= midIndex) {
            // 全部塞进去，因为都是排序好的
            temp[i++] = arr[leftIndex++];
        }
        // 如果遍历完了，但是右边还剩下一些元素
        while(rightIndex <= maxIndex) {
            // 全部塞进去，因为都是排序好的
            temp[i++] = arr[rightIndex++];
        }

        // 把辅助数组中的元素方到原数组中，要全部拿过去
        for(int j = 0;j <= maxIndex ; j++) {
            arr[j] = temp[j];
        }
    }
}
